/**
 * 733. 图像渲染
 * https://leetcode.cn/problems/flood-fill/description/
 */
class Solution {
    int[] dx = {0, 0, -1, 1};
    int[] dy = {-1, 1, 0, 0};
    int m, n;
    int flg;
    public int[][] floodFill(int[][] image, int sr, int sc, int color) {
        if(image[sr][sc] == color) return image;
        m = image.length;
        n = image[0].length;
        flg = image[sr][sc];
        image[sr][sc] = color;
        dfs(image, sr, sc, color);
        return image;
    }
    public void dfs(int[][] image, int i, int j, int color) {
        for(int k = 0; k < 4; k++) {
            int x = i + dx[k];
            int y = j + dy[k];
            if(x >= 0 && x < m && y >= 0 && y < n && image[x][y] == flg) {
                image[x][y] = color;
                dfs(image, x, y, color);
                //vist和image不用恢复现场
                // vist[x][y] = false;
                // image[x][y] = flg;
            }
        }
    }
}
//第一次写的版本，有些地方没必要加：vist
//class Solution {
//    int[] dx = {0, 0, -1, 1};
//    int[] dy = {-1, 1, 0, 0};
//    int m, n;
//    boolean[][] vist;
//    public int[][] floodFill(int[][] image, int sr, int sc, int color) {
//        if(image[sr][sc] == color) return image;
//        m = image.length;
//        n = image[0].length;
//        vist = new boolean[m][n];
//        int flg = image[sr][sc];
//        vist[sr][sc] = true;
//        image[sr][sc] = color;
//        dfs(image, sr, sc, color, flg);
//        return image;
//    }
//    public void dfs(int[][] image, int i, int j, int color, int flg) {
//        for(int k = 0; k < 4; k++) {
//            int x = i + dx[k];
//            int y = j + dy[k];
//            if(x >= 0 && x < m && y >= 0 && y < n && image[x][y] == flg && vist[x][y] == false) {
//                vist[x][y] = true;
//                image[x][y] = color;
//                dfs(image, x, y, color, flg);
//                //vist和image不用恢复现场
//                // vist[x][y] = false;
//                // image[x][y] = flg;
//            }
//        }
//    }
//}